package com.gxc.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 树的最大宽度
 */
public class MaximumWidth {

    public static void main(String[] args) {
        TreeBean tree = Preorder.createTree();

        //树的最大宽度  使用map记录节点的层数，需要额外空间
        maxWidth(tree);
        System.out.println("----------");
        //树的最大宽度  不使用额外空间
        maxWidthNoSpace(tree);
    }

    private static void maxWidthNoSpace(TreeBean tree) {
        //本层最后的节点
        TreeBean curEnd = null;
        //下一层最后的节点
        TreeBean nextEnd = null;
        //本层的节点数量
        int curNode = 0;

        Queue<TreeBean> queue = new LinkedList<>();
        queue.add(tree);
        curEnd = tree;
        curNode++;
        int maxNode = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            TreeBean treeBean = queue.poll();
            if (treeBean.left!=null) {
                queue.add(treeBean.left);
                nextEnd = treeBean.left;
            }
            if (treeBean.right!=null) {
                queue.add(treeBean.right);
                nextEnd = treeBean.right;
            }
            if (treeBean == curEnd) {
                curNode++;
                maxNode = Math.max(maxNode, curNode);
                curEnd = nextEnd;
                curNode = 0;
            } else {
                curNode++;
            }
        }
        System.out.println(maxNode);
    }

    /**
     * 树的最大宽度  使用map记录节点的层数，需要额外空间
     * @param tree
     */
    private static void maxWidth(TreeBean tree) {
        Queue<TreeBean> queue = new LinkedList<>();
        queue.add(tree);
        Map<TreeBean, Integer> levelMap = new HashMap<>();
        levelMap.put(tree, 1);
        int curLevel = 1;
        int curNode = 0;
        int maxNode = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            TreeBean treeBean = queue.poll();

            if (curLevel == levelMap.get(treeBean)) {
                curNode++;
            } else {
                maxNode = Math.max(maxNode, curNode);
                curLevel++;
                curNode = 1;
            }

            if (treeBean.left!=null) {
                levelMap.put(treeBean.left, curLevel+1);
                queue.add(treeBean.left);
            }
            if (treeBean.right!=null) {
                levelMap.put(treeBean.right, curLevel+1);
                queue.add(treeBean.right);
            }
        }
        System.out.println(maxNode);
    }

}
